/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 至多一次进行股票交易
 * 求最大利润。
 * 使用两指针，一个搜啊秒整个数组，另一个记录已扫描元素的最小值，扫描数组时一边移动，一边更新最大利润 O9n0
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class BestTimeBuySellStock {

 public int maxProfit(int[] prices) {
        int profit = 0;
        if(prices==null || prices.length==0){
            return profit;
        }
        //第一个指针记录最小值
        int min = prices[0];
        
        //第二个指针扫描整个数组
        for(int i=1;i<prices.length;i++){
            min = Math.min(min, prices[i]);
            profit = Math.max(profit, prices[i]-min);
        }
        return profit;
    }
}
